package com.bytearch.fast.cloud.algorithm.demo;

import com.bytearch.fast.cloud.algorithm.pojo.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉查找树
 */
public class BinarySearchTree {

    private TreeNode root;
    public void insertTreeNode(int data) {
        root = insert(root, data);
    }

    public TreeNode insert(TreeNode treeNode, int data) {
        if (treeNode == null)  return new TreeNode(data);
        if (data < treeNode.getData()) {
            //插左边
          treeNode.setLeftNode(insert(treeNode.getLeftNode(), data));
        } else if (data > treeNode.getData()) {
            //插右边
            treeNode.setRightNode(insert(treeNode.getRightNode(), data));
        } else {
            treeNode.setData(data);
        }
        return treeNode;
    }

    //深度优先遍历 包括前序遍历，中序遍历，后序遍历
    //前序遍历
    public void  preList(TreeNode node) {
        if (node == null) return;
        System.out.println(node.getData());
        preList(node.getLeftNode());
        preList(node.getRightNode());
    }

    //中序遍历
    public void  middleList(TreeNode node) {
        if (node == null) return;
        middleList(node.getLeftNode());
        System.out.println(node.getData());
        middleList(node.getRightNode());
    }
    //后序遍历
    public void  afterList(TreeNode node) {
        if (node == null) return;
        afterList(node.getLeftNode());
        afterList(node.getRightNode());
        System.out.println(node.getData());
    }
    //广度优先遍历
    public void breadthFirstList(TreeNode node) {
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.offer(node);
        while (!nodeQueue.isEmpty()) {
            TreeNode poll = nodeQueue.poll();
            //打印节点
            System.out.println(poll.getData());
            //子节点入队
            if (poll.getLeftNode() != null) {
                nodeQueue.offer(poll.getLeftNode());
            }
            if (poll.getRightNode() != null) {
                nodeQueue.offer(poll.getRightNode());
            }
        }
    }

    public static void main(String[] args) {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insertTreeNode(10);
        binarySearchTree.insertTreeNode(8);
        binarySearchTree.insertTreeNode(11);
        binarySearchTree.insertTreeNode(7);
        binarySearchTree.insertTreeNode(9);
        binarySearchTree.insertTreeNode(12);

        binarySearchTree.preList(binarySearchTree.root);
        System.out.println("===============");
        binarySearchTree.middleList(binarySearchTree.root);
        System.out.println("================");
        binarySearchTree.breadthFirstList(binarySearchTree.root);
    }
}
